from typing import List
import random

class Solution:
    def smallestK(self, arr: List[int], k: int) -> List[int]:
        if k == 0 or not arr:
            return []

        def partition(l, r):
            pivot_idx = random.randint(l, r)
            arr[l], arr[pivot_idx] = arr[pivot_idx], arr[l]
            pivot = arr[l]
            i = l
            for j in range(l + 1, r + 1):
                if arr[j] < pivot:
                    i += 1
                    arr[i], arr[j] = arr[j], arr[i]
            arr[l], arr[i] = arr[i], arr[l]
            return i

        def quickselect(l, r, k):
            if l <= r:
                idx = partition(l, r)
                if idx == k:
                    return
                elif idx > k:
                    quickselect(l, idx - 1, k)
                else:
                    quickselect(idx + 1, r, k)

        quickselect(0, len(arr) - 1, k)
        return arr[:k]

arr = [1, 3, 5, 7, 2, 4, 6, 8]
k = 4
print(Solution().smallestK(arr, k))
